/**
 * https://leetcode.cn/submissions/detail/571660291/
 * 543. 二叉树的直径
 * easy, 黄伟杰 2024.10.11
 * 树形DP
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int ans;
    int dfs(TreeNode *rt)
    {
        if (rt == nullptr)
            return 0;
        int L = dfs(rt->left);
        int R = dfs(rt->right);
        ans = max(ans, L + R + 1); // 寻找最长
        return max(R, L) + 1;      // 返回根的深度
    }

public:
    int diameterOfBinaryTree(TreeNode *root)
    {
        ans = 1;
        dfs(root);
        return ans - 1;
    }
};